﻿/*
题目: 最大同构子树

牛牛有一棵二叉树，其根节点为 root。牛牛想要在该二叉树中找到两棵子树，他们是同构的，且这两棵子树的大小是最大的。子树的大小为其节点个数。
两棵树是同构表示为该两棵树结构是相同的

https://www.nowcoder.com/questionTerminal/0069dafd4c7640e28b5f339136c11c2d
*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
#define EMPTY "$"

    int res;
    unordered_map<string, int> seq2len;

    // 返回当前子树的序列化
    string dfs(TreeNode* root) {
        if (root == nullptr) {
            return EMPTY;
        }

        string cur = std::to_string(root->val) +
            dfs(root->left) + dfs(root->right);

        // 判断一下是否存在重复
        if (seq2len.count(cur)) {
            res = max(res, seq2len[cur]);
        }
        else {
            // 否则计算一下长度，并计入哈希表
            int len = 0;
            for (int i = 0; i < cur.size(); i++) {
                if (::isdigit(cur[i]))  len++;
            }
            seq2len[cur] = len;
        }

        return cur;
    }

    // 树的序列化
    int maxSubTree(TreeNode* root) {
        res = 0;
        seq2len.clear();
        dfs(root);
        return res;
    }
};
